package string;

import java.util.Scanner;

/**
 * @ClassName Fibonacci_02
 * @Description TODO
 * @Author lenovo
 * @Date 2023-02-09 16:42
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class Fibonacci_02 {

    /**
     * 求斐波那契数列的第n项。
     斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     4 = f(3)+f(2)
     f(3) = f(2)+f(1)
     f(2) =1
     f(3) =2
     F(0) = 0；F(1) = 1；F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     给定 N，计算 F(N)。
     */
    /**
     * 状态方程解法
     *
     * @param n
     * @return
     */
    public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        int[] status = new int[2];
        status[0] = 0;
        status[1] = 1;

        int result = -1;
        for (int i = 2; i <= n; i++) {
            result = status[0] + status[1];
            status[0] = status[1];
            status[1] = result;
        }

        return result;
    }

    public static int fibonacci1(int n) {

        if (n == 0) return 0;
        if (n == 1) return 1;

        return fibonacci1(n - 1) + fibonacci1(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int next = sc.nextInt();
        System.out.println(fibonacci(next));
        System.out.println(fibonacci1(next));
    }

}